1. Field of the Invention
The present invention relates to a signal decoding system, a signal decoding method and a generation method of a lookup table for using in a signal decoding process. More specifically, the invention relates to a signal decoding system and a signal decoding method for performing a block decoding process of DCT coefficients.
2. Description of the Related Art
In general, upon encoding a video signal, video compression standards, such as MPEG (Moving Picture Experts Group) (1995, ISO/IEOp13818.2) and so forth have been widely used. In MPEG, a transform coding and a motion compensation are central principles for compression. Amongst, the transform coding is performed in the following manner. At first, a region of vertical eight pixels and horizontal eight pixels is referred to a pixel block. For the pixel block, a two-dimensional discrete cosine transformation (DCT) is performed to obtain a DCT coefficient block as a 8 by 8 matrix of DCT coefficients. Next, each coefficient in the DCT coefficient block is quantized on the basis of a predetermined quantization step. Each coefficient in the DCT coefficient block after quantization, are scanned in a predetermined scanning order for Huffman coding a set of the number, of successive zero coefficients (run) and a quantized value of the subsequent non-zero coefficient (level). The foregoing is the mechanism of coding.
On the other hand, on a decoding side, a bit stream thus coded is decoded in the following manner. At first, from the bit stream as a sequence of codewords, the code word is parsed. By performing a variable length decoding for the codeword, the corresponding set of the run and the level is obtained. Then, at a position in the block designated by a scanning order and the run, a inversely quantized value of the level is stored. In the foregoing block, in the position where the inversely quantized value is not stored, a value xe2x80x9czero (0)xe2x80x9d is stored.
Here, inverse quantization is a process for obtaining a DCT coefficient by performing multiplication of a predetermined quantization step and an element of quantization matrix after a correction of the doubled value of the level, and dividing the multiplication result by xe2x80x9c16xe2x80x9d (decimal number). It should be noted that the inverse quantization is defined by an MPEG standard.
In the following disclosure, the foregoing series of process will be referred to as a DCT coefficient block decoding. For the DCT coefficient block decoded as set forth above, an inverse discrete cosine transformation is performed to obtain a desired pixel block.
Conventionally, each process in the DCT coefficient block decoding is performed per each one block. FIG. 34 is a block diagram showing a construction of the conventional DCT coefficient block decoding system.
In FIG. 34, the conventional system includes a variable-length decoding unit 202 sequentially performing a variable-length decoding with serially reading a bit stream 201 to obtain a set of the run and the level in one block, a storage unit 204 storing the level or the value xe2x80x9c0xe2x80x9d at an appropriate position in the block on the basis of an obtained set 203 of the run and the level in one block and outputting a block 205, a inverse quantizing unit 206 performing inverse quantization for each coefficient in the block 205 for obtaining a DCT coefficient block 207. The variable-length decoding unit 202 includes a lookup table taking a set of the run and the level corresponding to one codeword and the codeword length as a table element.
Next, operation will be discussed with reference to FIG. 34. The bit stream 201 is inputted into the variable-length decoding unit 202. In the variable length decoding unit 205, a bit string which has a maximum length of one codeword is parsed from the bit stream 201, and then, a table element is specified for outputting the run and the level by using the parsed string as the table address.
Furthermore, using the code word length obtained by looking up the table, the lead of the next codeword is specified among the bit stream 201. The foregoing operation is repeated until a codeword xe2x80x9cEnd Of Block (EOB)xe2x80x9d which indicates the end of the non-zero coefficient appears. And, set 203 of the run and the level in one block is outputted.
In the storage unit 204, a DCT coefficient block where all coefficients have value xe2x80x9c0xe2x80x9d is preliminarily prepared. In the position determined by a scanning order and the run in the DCT coefficient block, the level is stored sequentially. The block 205 storing the levels in one block is inputted into the inverse quantizing unit 206. In the inverse quantizing unit 206, inverse quantization is performed with respect to all coefficients in the 8 by 8 matrix to output the DCT coefficient block 207.
On the other hand, a technique for speeding up variable-length decoding in the DCT coefficient block decoding has been disclosed in xe2x80x9cSuperscalar Huffman Decoder hardware Designxe2x80x9d (SPIE Vol. 2186, Image and Video Compression, pp. 38-47, 1994). In the above-identified publication, speeding up of variable-length decoding is achieved by simultaneously decoding multiple codewords.
FIG. 35 is a block diagram showing a construction of another conventional variable-length decoding system. In FIG. 35, the conventional system includes a bit string buffer 502 storing a bit stream 501, a table looking-up unit 504 for variable-length decoding and a lookup table 507.
In the bit string buffer 502, the bit stream 501 and an output 505 of the table looking-up unit 504 are inputted and a 17-bit string 503 whose length is maximum of one codeword is outputted.
The lookup table 507 has the table address 506 as the input and outputs the table element 508 identified by the address. The lookup table 507 is a table whose element has the set of the run and the level and a total codeword length corresponding to multiple codewords, and is constructed to obtain the sets of the run and the level and the total codeword length corresponding to all code codewords contained is the 17-bit string 506 by only one lookup operation.
The table looking-up unit 504 has a seventeen bit output 503 of the bit string buffer 502 as the input and outputs a bit string 503 as the table address 506. On the other hand, the table looking-up unit 54 has the table element 508 as the input and outputs multiple runs 509 and multiple levels 510 contained in the table element 508. Furthermore, the table looking-up unit 504 outputs a bit string 505 in which decoded codewords are excluded from the bit string 503.
Next, the opperation of the conventional system set forth above will be discussed with reference to FIG. 35. At first, the bit stream 501 is stored in the bit string buffer 502. The bit string buffer 5022 outputs the 17-bit string 503 from the lead of the bit stream 501 stored therein. The 17-bit string 503 is outputted as the table address 506 in the table looking-up unit 504. Then, by using the table address 506, the table element 508 in the lookup table 507 is identified. The obtained table element 508 is outputted as multiple runs 509 and multiple levels 510 in the table looking-up unit 504. In the table looking-up unit 504, further by using the total codeword length, the bit string 505 in which the decoded codewords are excluded from the 17-bit string 503 is returned to the bit string buffer 502. In the bit string buffer 502, the bit string 505 is concatenated with the lead of the stored bit stream 501.
AS shown in FIG. 34, the conventional DCT coefficient block decoding unit cannot start decoding the next codeword until the length of the codeword which is decoded currently is specified. Therefore, the variable-length decoding inherently becomes sequential processing per each codeword, so that the processing speed decreases.
On the other hand, as shown in FIG. 35, in the DCT coefficient block decoding, when all codewords contained in the 17-bit string read from the bit stream are decoded simultaneously, a huge amount of memory is necessary for the lookup table. Particularly, when the variable-length decoding is implemented as a software of a microprocessor, decoding performance may be degraded by cache-miss.
The present invention has been worked out for solving the drawbacks in the prior art. Therefore, it is an object of the present invention to provide a signal decoding system, a signal decoding method and a generation method of a lookup table for a signal decoding process which can achieve DCT coefficient block decoding at high speed.
According to the first aspect of the present invention, a signal decoding system comprises
decoding means for simultaneously performing variable length decoding process for multiple codewords; and
inverse quantization means for inversely quantizing multiple results obtained by the decoding means in parallel.
According to the second aspect of the present invention, a signal decoding method comprises:
decoding step of simultaneously performing variable length decoding process for multiple codewords; and
inverse quantization step of inversely quantizing multiple results obtained by the decoding means in parallel.
According to the third aspect of the present invention, a method of generating a lookup table to be used in variable length decoding, comprises:
step of, when concatenated two codewords equals a prefix in K bit (K is an integer greater than or equal to two and less than seventeen) representation of a table address value, runs and levels respectively corresponding to the two code words and the total length of concatenated two codewords are stored in the corresponding table address;
step of, when concatenated two codewords do not equals a prefix in K bit representation of a table address value and when the first one of the two codewords equals a prefix of the K bit representation, run and level corresponding to the one codeword and the length of the codeword are stored in the corresponding table address;
step of, when concatenated two codewords do not equal a prefix in K bit representation of a table address value and when the first one of the two codewords does not equals the prefix of the K bit representation, a dummy data is stored in the table address,
the steps being performed for all table addresses of the lookup table.
In short, in the present invention, variable length decoding and inverse quantization for multiple codewords are performed in parallel. More particularly, variable length decoding of multiple codewords is performed simultaneously, and inverse quantization of multiple levels obtained by the decoding means can be performed in parallel. Thus, by performing variable length decoding and inverse quantization for multiple codewords simultaneously, variable length decoding in one by one basis can be avoided to improve processing speed of the DCT coefficient block decoding. Besides, by performing inverse quantization only for the levels, the DCT coefficient block decoding can be speeded up in comparison with the conventional system.
On the other hand, by restricting the number of codewords decoded simultaneously to be less than or equal to two and using the lookup table having small memory capacity, memory cost can be reduced. Particularly, when the variable length decoding is implemented by software of a microprocessor, decoding performance can be degraded due to cache miss. In addition, by combining parallel variable length decoding means and parallel inverse quantization means, faster DCT coefficient block decoding can be achieved comparing with the conventional system. It should be noted that the inverse quantization means are suitable for software implementation on the microprocessors which have parallel operation instructions.